package org.xiaoxin.leetcode.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * LeetCode 1. 两数之和
 * <p>
 * 题目描述：
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 * <p>
 * 难度：简单
 * 标签：数组、哈希表
 *
 * @author xiaoxin
 */
public class _001_TwoSum {

    /**
     * 解法一：暴力解法
     * 思路：双重循环遍历数组，找到两个数的和等于目标值
     * 时间复杂度：O(n²)
     * 空间复杂度：O(1)
     */
    public int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    /**
     * 解法二：哈希表（一次遍历）
     * 思路：使用哈希表存储已遍历的元素及其索引，查找target-当前元素是否存在
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        _001_TwoSum solution = new _001_TwoSum();

        // 测试用例1
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        System.out.println("测试用例1:");
        System.out.println("输入: nums = " + Arrays.toString(nums1) + ", target = " + target1);
        System.out.println("解法一: " + Arrays.toString(solution.twoSum1(nums1, target1)));
        System.out.println("解法二: " + Arrays.toString(solution.twoSum2(nums1, target1)));

        // 测试用例2
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        System.out.println("\n测试用例2:");
        System.out.println("输入: nums = " + Arrays.toString(nums2) + ", target = " + target2);
        System.out.println("解法一: " + Arrays.toString(solution.twoSum1(nums2, target2)));
        System.out.println("解法二: " + Arrays.toString(solution.twoSum2(nums2, target2)));

        // 测试用例3
        int[] nums3 = {3, 3};
        int target3 = 6;
        System.out.println("\n测试用例3:");
        System.out.println("输入: nums = " + Arrays.toString(nums3) + ", target = " + target3);
        System.out.println("解法一: " + Arrays.toString(solution.twoSum1(nums3, target3)));
        System.out.println("解法二: " + Arrays.toString(solution.twoSum2(nums3, target3)));
    }
} 